#include <iostream>

using namespace std;

template <typename T>
void selectionSort(T arr[], size_t begin, size_t end){
	size_t index;
	T temp;
	for(int i  = end; i > begin; i --){
		index = i;
		for(int j = begin; j < i; j ++){
			if(arr[j] > arr[index])
				index = j;
		}
		if(index == i)
			continue;
		temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
	}
}


void testSelectionSort(){
	int arr[] = {3, 2, 5, 6, 9, 1, 4, 8, 10, 12};
	int size = sizeof(arr) / sizeof(int);
	selectionSort<int>(arr, 0, size - 1);

	int index = 0;
	while(index <size)
		cout << arr[index ++] << endl;
	getchar();
}